Image satellite planning is a planning process used to determine the pointing path that an imaging satellite takes as it passes over a set of targets on the ground. In many imaging satellite planning problems, there are more targets on the ground than the satellite can point to and image in the amount of time that the satellite is able to view the targets. Thus, a subset of targets are selected and ordered, based on the value and location of the targets, to provide the highest value targets at the lowest cost. The problem of determining the optimal set of ordered targets that the satellite should image during its pass can be categorized as a traveling salesman problem.
The traveling salesman problem as proposed by Karl Menger's “Botenproblem” was presented in Vienna in 1930. A salesman travels to a set of cities, and incurs a cost for traveling from one city to the next city. The problem is determining the order in which he should travel to the cities, to minimize the cost of traveling between them. The best solution is an ordered subset of the cities that minimizes the total cost to travel to all of the cities. This is a member of the class of mathematical problems that are known as NP-complete (non-polynomial time complete). Even for a moderately complicated NP-complete problem, the computation of the optimal solution using modern computers may require billions of years.
A variation of the traveling salesman problem is when there are more cities or stores to call on than the salesman can visit in a given week. Thus, the solution requires not only putting the stores in the best order, but also selecting which stores the salesman should skip. At each store the number of sales the salesman makes is proportional to the amount of product the individual store has sold since the salesman's last visit. The sales rate for each store is different, and the cost of going from one store to the next is unique. The problem is determining on each given day what stores does the salesman call on and in which order, such that the maximum value of stores for the minimum cost is achieved. This is the form of the traveling salesman problem that is solved in deciding which targets a satellite collects in a given pass over a data rich area.
An example of a data rich environment is the surveillance of all the gasoline stations in Los Angeles County. The value of imaging a particular gas station is proportional to the number of days since the last image was taken, multiplied by the number of pumps at the gas station. Thus, the value of each gas station is different. The cost to image a particular station is the time to reorient the satellite from gas station A to point to gas station B. Thus, the cost of reorienting the satellite between any two gas stations is different. The desired solution is an ordered subset of targets that maximizes the total value of the imaged targets and minimizes the cost. FIG. 1 shows a typical set of targets 12 and the satellite pointing path 14 to collect the selected targets 12a, 12b, 12c, etc.
The computation time to solve this problem for the best solution usually exceeds the amount of time available between imaging windows. That is, the best solution cannot be derived before the satellite is passing over the targets again. Therefore, an iterative approximation to the solution is used. Each iteration through the traveling salesman algorithm searches for a subset of targets that increases the sum of the values of the images, without the sum of the maneuver times or the imaging times exceeding the imaging window time (the amount of time that the satellite is available to view the targets).
Some prior art methods of solving this problem use a two-step process. First, the problem is iterated to obtain an ordered subset of targets with a high total value and low cost. This solution is not necessarily the most optimal solution to the problem, but it is the best solution that the iterative approximation can locate during the limited time between satellite imaging passes. Second, the ordered subset is validated through a more detailed simulation that makes small timing corrections. The final ordered subset is then transmitted to the satellite to execute.
However, the iterative process cannot fully explore the traveling salesman problem before the calculation window is over and the list of targets is validated and sent to the satellite to execute. Accordingly, there is a need for an improved method of solving the satellite imaging problem.